The electronic collection and storage of information presents problems in many environments. For example, when clinical data is collected from a patient through a patient monitor, vast amounts of data can be collected during a short interval. A computer system typically stores this data in computer memory for later processing. The computer memory has a limited capacity and can quickly fill up with the collected data.
To reduce the memory requirements of collected data, some computer systems compress data before storing it in the computer memory. When the collected data is needed for processing, the computer system decompresses the data. Thus, while the data is not needed, the memory requirements are minimized. Similarly, to reduce data transmission time, data is transmitted from one computer to another in compressed format. The receiving computer then decompresses the data before processing.
Many compression and decompression methods are known. Various methods have a variety of advantages. For example, some methods generate a large reduction in data size. Other methods preserve all the original data through the compression and decompression process. These methods are referred to as being lossless because no data is lost. Other methods compress data very quickly or decompress data very quickly. These various methods also have a variety of disadvantages. For example, some methods do not generate a large reduction in data size. Other methods do not preserve all the original data through the compression and decompression process; that is, the decompressed data is only an approximation of the original data. Also, some methods compress or decompress slowly. Some methods use considerable computer memory when compressing or decompressing. Some methods are usable for specific types of data, e.g., ASCII text or electrocardiogram wave forms.
Some compression and decompression methods use a fixed-length encoding, while others use a variable-length encoding. A fixed-length encoding method represents each symbol by the same number of bits. For example, the American Standard Code Information for Interchange (ASCII) is a fixed-length encoding. The ASCII standard specifies that each character is represented by 8 bits. A variable-length encoding method represents the symbols by a varying number of bits. For example, the well-known Morse code is a variable-length encoding.
Fixed-length and variable-length encoding methods each have advantages and disadvantages. A major advantage of a variable-length encoding is that it produces a smaller encoded data buffer than a fixed-length encoding. Variable-length encoding methods typically assign shorter codes to more frequently used symbols. A major advantage of fixed-length encoding is that the encoding and decoding are particularly efficient when performed by a computer system. For example, when the code length is a multiple of a byte length, then bit manipulations (e.g., shifting) that are necessary for variable-length codes are not needed.
It would be desirable to have an encoding scheme that is not dependent on the type of data, that produces small compressed data buffers, and that allows for efficient decoding.